#include <stdio.h>

#define UNKNOWN -1
#define MAX_N 45

// 全局记忆化存储数组
int knownF[MAX_N];


int F(int i);

int F2(int i);
void init_fib();

int main(int argc, char** argv){
    init_fib();
    printf("%d\n", F2(40));
    return 0;
}


void init_fib(){
    int i;
    for (i = 0; i < MAX_N; i++) {
        knownF[i] = UNKNOWN;
    }
}

int F2(int i){
    if (knownF[i] != UNKNOWN) {
        return knownF[i];
    }
    int t;
    if (i < 1) {
        t = 0;
    }else if (i == 1) {
        t = 1;
    }else {
        t = F2(i-1)+F2(i-2);
    }
    knownF[i] = t;
    return t;
}

int F(int i){
    if (i < 1) {
        return 0;
    }
    if (i == 1) {
        return 1;
    }
    return F(i-1) + F(i-2);
}

